In recent research concerning computer architectures wherein a plurality of processors or component computers are operated in parallel to achieve high rates of throughput, much of the effort has concerned the integration of a network of busses for interconnecting the parallel processors. The processors are either tightly or loosely coupled, depending upon whether or not they share memory and operating tasks. Among tightly coupled computers crossbar switch networks provides better interconnections than do multi-stage networks of any other type presently known.
Two approaches have been taken in the prior art with regard to constructing crossbar switch networks in monolithic integrated circuitry. One has been to construct a 2-crosspoint-by-2-crosspoint network in each of a plurality of bit slices on each integrated circuit to be used with a number of similar crossbar switch network component integrated circuits. This approach requires N.sup.2 /4 integrated circuits to form an N-crosspoint-by-N-crosspoint crossbar switch network and demands the order of N in number of routing stages for each connection. The other approach has been to construct an N-crosspoint-by-N-crosspoint crossbar switch network in one or more bit slices on each integrated circuit.
There are practical constraints on N when the latter approach is taken. The area of the integrated circuit tends to grow at the rate of N.sup.2, where N is the number of output ports as well as the number of input ports. The limitation upon the size of N normally is not imposed by this area increase, but rather upon the slower linear rate of increase in the perimeter of the integated circuit die, which limits the number of connections it is practical to make to it. The crossbar switch arranges for each of its output ports to connect to one of its input ports, one of which "input ports" may be just non-connection to any of (N-1) actual input ports. Since one (or none) of the N crosspoint switches associated with each output port can be specified by a digital code of log.sub.2 N bits, N log.sub.2 N pins are required to be able to select in real time the crosspoint switch for each of the N output ports. Crossbar switches with 256 crosspoint switches requiring sixteen input data pins, sixteen output data pins and sixty-four control pins have been about as large as is practical to realize with integrated circuit packages now available.
It is desirable to construct crossbar switches with a larger number of crosspoints on each integrated circuit die, such that it is the limitation of the N.sup.2 rate of increase in die area rather than the limitation on "pin-out" (i.e., the limitation on the number of pins) that determines the maximum number of network crosspoints per die. Being able to do this is based in large part on there being a way to reduce pin-out requirements. Inter-die electrical connections provided by pin-out to a printed-circuit board and pin-in from a printed-circuit board are generally more costly and less reliable than intra-die electrical connections.
An approach that has been taken to reduce pin-out requirements is to include a control pattern memory on the same integrated circuit with the crossbar switch for storing (Nlog.sub.2 N)-bit selection signals for the crossbar switch. This was done in the LINC integrated-circuit described by C-Y Chin, the present inventors and others in the paper "A Dynamically Reconfigurable Interconnection Chip" presented publicly Feb. 27, 1987 and reported on pages 276, 277 and 425 of the Digest of Technical Papers, 1987 IEEE International Solid-State Circuits. Each of the N output ports of the crossbar switch can connect to any of its N input ports (one of which input ports may be first non-connection to any of the other input ports), so there are N permutations per output port that can combine with a previous set or previous sets of those permutations, so there are N.sup.N possible patterns for connection by the crossbar switch. If all N.sup.N possible control patterns for generating such crossbar switch connections were stored in memory, NlogN bits would be required to code all possible addreses of the memory locations storing these N.sup.N control patterns. This would provide no saving in pin-out. Furthermore, the memory having N.sup.N locations each storing an Nlog.sub.2 N bit pattern would have to have N.sup.(N-1) log.sub.2 N bit storage capability, which is substantially large for N larger than sixteen. This approach has been taken, however, when the number of possible interconnection patterns can be restricted to substantially fewer than N.sup.N. For example, in a barrel shifter there are only N interconnection patterns of interest. Memory size is only N.sup.2 log.sub.2 N bits, and only log.sub.2 N bits are needed to address each of the N possible patterns in the pattern memory.
In the LINC integrated-circuit the control pattern memory is divided into two banks that can be selectively conditioned, one for reading from and the other for writing into, to allow control pattern memory updating without having to interrupt data flow through the crossbar switch. The writing of memory is done N parallel bits at a time in the LINC integrated-circuit described in the February 1987 ISSCC paper, N being eight.
The inclusion of memory for controlling the crosspoint switches in a monolithic integrated circuit permits time-division multiplexing of write-input signal to the memory with data processing functions, the inventors point out. This allows reflexing of the write-input signal of the memory through a data port or data ports of the integrated circuit, so that the pin count of the die need not increase to include further pins for writing memory. Reflexing of the memory write input could be wholly or in part through the N-bit-wide output data port of the integrated crossbar switch, but low-output-impedance output data buffer amplifiers tend to make this difficult. Preferably, reflexing of the memory write is done entirely through the N-bit-wide input data port of the integrated crossbar switch. Such reflexing is not difficult to do despite the use of input data buffer amplifiers, since these amplifiers are usually high-input impedance types. (Indeed, reflexing may be done after rather than before the input data buffer amplifiers, if one so chooses).
The size of the memory needed to control the connection patterns of the crosspoint switches is reduced to a minimal N.sup.2 bits in accordance with the invention by assigning a respective single-bit storage location in memory to each crosspoint switch. This eliminates the need for control pattern decoders between memory and the crosspoint switches, a requirement in the LINC integrated circuit. Just the N.sup.2 bits of memory allow the storage of all possible interconnection patterns in the crossbar switch. The (N.sup.2)-bit memory is "square" and is invariably addressable using two orthogonal addresses of similar bit-width, while the prior art control pattern memories often may not be "square", making it more difficult to address them efficiently.
The trade-off in performance is that the updating of connection patterns is slower in the one-storage-location-per-crosspoint (or N.sup.2 -bit) memory than in the larger connection pattern memory if the new connection pattern is any arbitrary one that does not lend itself to updating the memory on an N-parallel-bits basis. However, in many instances changes in the routing of digital sampled-data signals through a crossbar switch network occur relatively rarely as compared to sampling rate. The conditions of the cross-point switches then do not need to be modified all at one time, but may instead be modified sequentially using row-and-column addressing of the switches. Row-and-column addressing, or addressing with any other two orthogonal variables descriptive of cross-point location, requires only 2 log.sub.2 N control pins since location can be coded for both dimensions of memory addressing. In many applications both of the two orthogonal addresses of similar log.sub.2 N bit-width may be introduced into the integrated circuit through the same pins on a time-division-multiplexed basis, the inventors point out. For changes of connection of only one output port at an isolated time, the slower nature of updating the crossbar connection pattern from N.sup.2 -bit memory will not manifest itself. Also arrangements can be made to change between certain patterns of interconnection without the slower nature of updating from N.sup.2 -bit memory manifesting itself.
There are specialized applications of crossbar switches in which the number of control pins can be reduced because not all patterns of output ports connecting to input ports are encountered. An example of this is the use of the crossbar switch as a programmable barrel-shifter, which is described in detail further on in the specification, which allows the number of control pins to be reduced to the order of log.sub.2 N in number.
It is useful to distribute the memory used for controlling the crosspoint switches in the integrated circuit. By associating a respective single-bit storage cell in memory with each cross-point switch being controlled, so that each addressable storage cell controls the switching of the cross-point switch with which it is associated, and locating each set of associated elements within the confines of a respective one of close-packed cells, the integrated circuitry becomes regular in its pattern. Therefore, layout can be done on a step-and repeat basis, which facilitates the layout of crossbar switches using a silicon compiler.